import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-26
 * Time: 10:07
 */

public class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        long result = 0;
        // 左右各维护一个小根堆
        PriorityQueue<Integer> front = new PriorityQueue<>();
        PriorityQueue<Integer> end = new PriorityQueue<>();
        int len = costs.length;
        int left = 0;
        int right = len - 1;
        while (k > 0) {
            // 这两个循环里面必须都取 ==
            // 因为 此时里面的 left 和 right 都是待使用的值,
            // 如果不取等, 都可能使得原本该被加入到队列中的没加入到队列中
            while (front.size() < candidates && left <= right) {
                front.add(costs[left]);
                left++;
            }
            while (end.size() < candidates && right >= left) {
                end.add(costs[right]);
                right--;
            }
            // 左右两个队列中的元素个数可能不太相同, 所以可能某个队列先为 空了
            // 这里就体现了 元素的下标的值会变化
            int l = front.isEmpty() ? Integer.MAX_VALUE : front.peek();
            int r = end.isEmpty() ? Integer.MAX_VALUE : end.peek();
            if (l <= r) {
                result += front.poll();
            } else {
                result += end.poll();
            }
            k--;
        }
        return result;
    }
}
